// 题目描述
// 74. 搜索二维矩阵
// 难度
// 中等
// 814
// 给你一个满足下述两条属性的 m x n 整数矩阵：
// 每行中的整数从左到右按非递减顺序排列。
// 每行的第一个整数大于前一行的最后一个整数。
// 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
//   示例 1：
// 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
// 输出：true
// 示例 2：
// 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
// 输出：false
//   提示：
// m == matrix.length
// n == matrix[i].length
// 1 <= m, n <= 100
// -104 <= matrix[i][j], target <= 104
// 通过次数318,133提交次数652,843

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  const helper = (arr) => {
    let left = 0
    let right = arr.length - 1
    while (left <= right) {
      const mid = left + Math.floor((right - left) / 2)
      if (arr[mid] === target) {
        return true
      } else if (arr[mid] < target) {
        left = mid + 1
      } else if (arr[mid] > target) {
        right = mid - 1
      }
    }

    return false
  }

  for (const line of matrix) {
    if (line[0] > target) {
      continue
    }

    if (helper(line)) {
      return true
    }
  }

  return false
}

console.log(
  searchMatrix(
    [[1,3,5,7],[10,11,16,20],[23,30,34,60]],
    13
  )
)
